home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CTOOLS10.ARJ / LIST.C < prev    next >
C/C++ Source or Header  |  1991-12-31  |  11KB  |  347 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: list.c $
  7. * Version:        $Revision: 1.9 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Module to implement linked lists. Includes a routine to
  13. *                peform a mergesort on the linked list.
  14. *
  15. * $Id: list.c 1.9 91/12/31 19:40:15 kjb Exp $
  16. *
  17. * Revision History:
  18. * -----------------
  19. *
  20. * $Log:    list.c $
  21. * Revision 1.9  91/12/31  19:40:15  kjb
  22. * Modified include file directories.
  23. * 
  24. * Revision 1.8  91/10/28  03:17:14  kjb
  25. * Ported to the Iris.
  26. * 
  27. * Revision 1.7  91/09/03  18:28:15  ROOT_DOS
  28. * Ported to UNIX.
  29. * 
  30. * Revision 1.6  91/09/01  17:31:07  ROOT_DOS
  31. * Fixed bug in lst_deletenext().
  32. * 
  33. * Revision 1.5  91/09/01  17:17:37  ROOT_DOS
  34. * Changed lst_deletenext() to return a pointer to the deleted node's
  35. * userspace.
  36. * 
  37. * Revision 1.4  91/09/01  16:04:09  ROOT_DOS
  38. * Minor cosmetic change
  39. * 
  40. * Revision 1.3  91/09/01  01:49:59  ROOT_DOS
  41. * Changed search for include files to search the current directory.
  42. * 
  43. * Added function lst_kill() to delete the nodes in the list, calling a user
  44. * supplied function to kill each node.
  45. * 
  46. * Revision 1.2  91/08/21  14:32:02  ROOT_DOS
  47. * Optimized the mergesort routine by eliminating passing the end of the
  48. * merged list found in merge(), back to the main mergesort() routine. This
  49. * eliminated the need to traverse the newly merged list to find the end. 
  50. * Gives about 10% speed improvement for moderate size lists.
  51. * 
  52. * Revision 1.1  91/08/21  14:10:39  ROOT_DOS
  53. * Initial revision
  54. * 
  55. ****************************************************************************/
  56.  
  57. #include <stdio.h>
  58. #include <malloc.h>
  59. #include <signal.h>
  60. #include "debug.h"
  61. #include "list.h"
  62.  
  63. PUBLIC void *lst_newnode(int size)
  64. /****************************************************************************
  65. *
  66. * Function:        lst_newnode
  67. * Parameters:    size    - Amount of memory to allocate for node
  68. * Returns:      Pointer to the allocated node's user space.
  69. *
  70. * Description:    Allocates the memory required for a node, adding a small
  71. *                header at the start of the node. We return a reference to
  72. *                the user space of the node, as if it had been allocated via
  73. *                malloc().
  74. *
  75. ****************************************************************************/
  76. {
  77.     LST_BUCKET    *node;
  78.  
  79.     if ( !(node = (LST_BUCKET*)malloc(size + sizeof(LST_BUCKET))) ) {
  80.         fprintf(stderr,"Not enough memory to allocate list node.\n");
  81.         raise(SIGABRT);
  82.         return NULL;
  83.         }
  84.  
  85.     return LST_USERSPACE(node);            /* Return pointer to user space */
  86. }
  87.  
  88. PUBLIC void lst_freenode(void *node)
  89. /****************************************************************************
  90. *
  91. * Function:        lst_freenode
  92. * Parameters:    node    - Node to free.
  93. *
  94. * Description:  Frees a node previously allocated with lst_newnode().
  95. *
  96. ****************************************************************************/
  97. {
  98.     free(LST_HEADER(node));
  99. }
  100.  
  101. PUBLIC LIST *lst_init(void)
  102. /****************************************************************************
  103. *
  104. * Function:        lst_init
  105. * Returns:      Pointer to a newly created list.
  106. *
  107. * Description:    Initialises a list and returns a pointer to it.
  108. *
  109. ****************************************************************************/
  110. {
  111.     LIST    *l;
  112.  
  113.     if ((l = (LIST*)malloc(sizeof(LIST))) != NULL) {
  114.         l->count = 0;
  115.         l->head = &(l->hz[0]);
  116.         l->z = &(l->hz[1]);
  117.         l->head->next = l->z->next = l->z;
  118.         }
  119.     else {
  120.         fprintf(stderr,"Insufficient memory to allocate list\n");
  121.         raise(SIGABRT);
  122.         return NULL;
  123.         }
  124.  
  125.     return l;
  126. }
  127.  
  128. PUBLIC void lst_kill(LIST *l,void (*freeNode)(void *node))
  129. /****************************************************************************
  130. *
  131. * Function:        lst_kill
  132. * Parameters:    l            - List to kill
  133. *                freeNode    - Pointer to user routine to free a node
  134. *
  135. * Description:    Kills the list l, by deleting all of the elements contained
  136. *                within the list one by one and then deleting the list
  137. *                itself. Note that we call the user supplied routine
  138. *                (*freeNode)() to free each list node. This allows the user
  139. *                program to perform any extra processing needed to kill each
  140. *                node (if each node contains pointers to other items on the
  141. *                heap for example). If no extra processing is required, just
  142. *                pass the address of lst_freenode(), ie:
  143. *
  144. *                    lst_kill(myList,lst_freenode);
  145. *
  146. ****************************************************************************/
  147. {
  148.     LST_BUCKET    *n,*p;
  149.  
  150.     n = l->head->next;
  151.     while (n != l->z) {            /* Free all nodes in list                */
  152.         p = n;
  153.         n = n->next;
  154.         (*freeNode)(LST_USERSPACE(p));
  155.         }
  156.     free(l);                    /* Free the list itself                    */
  157. }
  158.  
  159. PUBLIC void lst_insertafter(LIST *l,void *node,void *after)
  160. /****************************************************************************
  161. *
  162. * Function:        lst_insertafter
  163. * Parameters:    l        - List to insert node into
  164. *                node    - Pointer to user space of node to insert
  165. *                after    - Pointer to user space of node to insert node after
  166. *
  167. * Description:    Inserts a new node into the list after the node 'after'. To
  168. *                insert a new node at the beginning of the list, user the
  169. *                macro LST_HEAD in place of 'after'. ie:
  170. *
  171. *                    lst_insertafter(mylist,node,LST_HEAD(mylist));
  172. *
  173. ****************************************************************************/
  174. {
  175.     LST_BUCKET    *n = LST_HEADER(node),*a = LST_HEADER(after);
  176.  
  177.     n->next = a->next;
  178.     a->next = n;
  179.     l->count++;
  180. }
  181.  
  182. PUBLIC void *lst_deletenext(LIST *l,void *node)
  183. /****************************************************************************
  184. *
  185. * Function:        lst_deletenext
  186. * Parameters:    l        - List to delete node from.
  187. *                node    - Node to delete the next node from
  188. * Returns:        Pointer to the deleted node's userspace.
  189. *
  190. * Description:    Removes the node AFTER 'node' from the list l.
  191. *
  192. ****************************************************************************/
  193. {
  194.     LST_BUCKET    *n = LST_HEADER(node);
  195.  
  196.     node = LST_USERSPACE(n->next);
  197.     n->next = n->next->next;
  198.     l->count--;
  199.     return node;
  200. }
  201.  
  202. PUBLIC void *lst_first(LIST *l)
  203. /****************************************************************************
  204. *
  205. * Function:        lst_first
  206. * Parameters:    l        - List to obtain first node from
  207. * Returns:        Pointer to first node in list, NULL if list is empty.
  208. *
  209. * Description:    Returns a pointer to the user space of the first node in
  210. *                the list. If the list is empty, we return NULL.
  211. *
  212. ****************************************************************************/
  213. {
  214.     LST_BUCKET    *n;
  215.  
  216.     n = l->head->next;
  217.     return (n == l->z ? NULL : LST_USERSPACE(n));
  218. }
  219.  
  220. PUBLIC void *lst_next(void *prev)
  221. /****************************************************************************
  222. *
  223. * Function:        lst_next
  224. * Parameters:    prev    - Previous node in list to obtain next node from
  225. * Returns:        Pointer to the next node in the list, NULL at end of list.
  226. *
  227. * Description:    Returns a pointer to the user space of the next node in the
  228. *                list given a pointer to the user space of the previous node.
  229. *                If we have reached the end of the list, we return NULL. The
  230. *                end of the list is detected when the next pointer of a node
  231. *                points back to itself, as does the dummy last node's next
  232. *                pointer. This enables us to detect the end of the list
  233. *                without needed access to the list data structure itself.
  234. *
  235. *                NOTE:    We do no checking to ensure that 'prev' is NOT a
  236. *                        NULL pointer.
  237. *
  238. ****************************************************************************/
  239. {
  240.     LST_BUCKET    *n = LST_HEADER(prev);
  241.  
  242.     n = n->next;
  243.     return (n == n->next ? NULL : LST_USERSPACE(n));
  244. }
  245.  
  246. /* Static globals required by merge()    */
  247.  
  248. static LST_BUCKET    *z;
  249. static int             (*cmp)(void*,void*);
  250.  
  251. PRIVATE LST_BUCKET *merge(LST_BUCKET *a,LST_BUCKET *b,LST_BUCKET **end)
  252. /****************************************************************************
  253. *
  254. * Function:        merge
  255. * Parameters:    a,b        - Sublist's to merge
  256. * Returns:        Pointer to the merged sublists.
  257. *
  258. * Description:    Merges two sorted lists of nodes together into a single
  259. *                sorted list.
  260. *
  261. ****************************************************************************/
  262. {
  263.     LST_BUCKET    *c;
  264.  
  265.     /* Go through the lists, merging them together in sorted order    */
  266.  
  267.     c = z;
  268.     while (a != z && b != z) {
  269.         if ((*cmp)(LST_USERSPACE(a),LST_USERSPACE(b)) <= 0) {
  270.             c->next = a; c = a; a = a->next;
  271.             }
  272.         else {
  273.             c->next = b; c = b; b = b->next;
  274.             }
  275.         };
  276.  
  277.     /* If one of the lists is not exhausted, then re-attach it to the end
  278.      * of the newly merged list
  279.      */
  280.  
  281.     if (a != z) c->next = a;
  282.     if (b != z) c->next = b;
  283.  
  284.     /* Set *end to point to the end of the newly merged list    */
  285.  
  286.     while (c->next != z) c = c->next;
  287.     *end = c;
  288.  
  289.     /* Determine the start of the merged lists, and reset z to point to
  290.      * itself
  291.      */
  292.  
  293.     c = z->next; z->next = z;
  294.     return c;
  295. }
  296.  
  297. PUBLIC void lst_mergesort(LIST *l,int (*cmp_func)(void*,void*))
  298. /****************************************************************************
  299. *
  300. * Function:        lst_mergesort
  301. * Parameters:    l            - List to merge sort
  302. *                cmp_func    - Function to compare two user spaces
  303. *
  304. * Description:    Mergesort's all the nodes in the list. 'cmp' must point to
  305. *                a comparison function that can compare the user spaces of
  306. *                two different nodes. 'cmp' should work the same as
  307. *                strcmp(), in terms of the values it returns.
  308. *
  309. ****************************************************************************/
  310. {
  311.     int            i,N;
  312.     LST_BUCKET    *a,*b;        /* Pointers to sublists to merge            */
  313.     LST_BUCKET    *c;            /* Pointer to end of sorted sublists        */
  314.     LST_BUCKET    *head;        /* Pointer to dummy head node for list        */
  315.     LST_BUCKET    *todo;        /* Pointer to sublists yet to be sorted        */
  316.     LST_BUCKET    *t;            /* Temporary                                */
  317.  
  318.     /* Set up globals required by merge() and pointer to head    */
  319.  
  320.     z = l->z; cmp = cmp_func; head = l->head;
  321.  
  322.     for (N = 1,a = z; a != head->next; N = N + N) {
  323.         todo = head->next; c = head;
  324.         while (todo != z) {
  325.  
  326.             /* Build first sublist to be merged, and splice from main list
  327.              */
  328.  
  329.             a = t = todo;
  330.             for (i = 1; i < N; i++) t = t->next;
  331.             b = t->next; t->next = z; t = b;
  332.  
  333.             /* Build second sublist to be merged and splice from main list
  334.              */
  335.  
  336.             for (i = 1; i < N; i++) t = t->next;
  337.             todo = t->next; t->next = z;
  338.  
  339.             /* Merge the two sublists created, and set 'c' to point to the
  340.              * end of the newly merged sublists.
  341.              */
  342.  
  343.             c->next = merge(a,b,&t); c = t;
  344.             }
  345.         }
  346. }
  347.